package weektwo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindSubsetsII_90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans = new ArrayList<>();
        set = new ArrayList<>();
        Arrays.sort(nums);
        findSubsets(nums, 0, false);
        return ans;
    }

    private List<List<Integer>> ans;
    private List<Integer> set;

    // public List<List<Integer>> subsets(int[] nums) {
    //     ans = new ArrayList<List<Integer>>();
    //     set = new ArrayList<Integer>();
    //     findSubsets(nums, 0);
    //     return ans;
    // }

    private void findSubsets(int[] nums, int index, boolean choosedPre) {
        if (index == nums.length) {
            ans.add(new ArrayList<Integer>(set));
            return;
        }
        //不选第一个
        findSubsets(nums, index + 1, false);
        //没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
        if (!choosedPre && index > 0 && nums[index] == nums[index - 1]) {
            return;
        }

        set.add(nums[index]);
        //选择第一个
        findSubsets(nums, index + 1, true);
        set.remove(set.size() - 1);
    }
}
